package com.gary.sort;

import java.util.Arrays;

/**
 *  递归实现归并排序算法
 *      归并：分而治之
 *          首先将数组一分为二，拟定两个指针，分别指向两部分的最右侧
 *          开辟一个新的与r - l + 1大小相同的数组，
 *   merge: 核心比较指针位置的大小，小的填入新的数组，指针位置++，当数组越界时结束对比
 * @author peng_rui
 * @date 2022/3/2
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5,1,6,3,8,7,4,0,9};
        process(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void process(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1); //去中位数
        process(arr, left, mid);
        process(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        int i = 0;
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
    }
}
